Lowest Common Ancestor

定义 Definition

lowest common ancestor（最近公共祖先）：在一棵树（tree）结构中，同时是两个节点祖先（ancestor）的节点里，离这两个节点最近（最深）的那个节点。常用于计算机科学中的树、二叉树与图论算法（通常简称 LCA）。

例句 Examples

In this tree, the lowest common ancestor of nodes 4 and 5 is node 2.
在这棵树中，节点 4 和节点 5 的最近公共祖先是节点 2。

To answer many queries efficiently, we preprocess the tree so each lowest common ancestor can be found in logarithmic time.
为了高效回答大量查询，我们会先对树进行预处理，使得每次查询最近公共祖先都能在对数时间内完成。

发音 Pronunciation (IPA)

/ˈloʊɪst ˈkɑːmən ˈænsɛstər/

词源 Etymology

该术语由三个常见英语词组合而成：lowest（最低/最深）、common（共同的）、ancestor（祖先）。在树结构语境中，“lowest”并非指物理高度，而是指在树中深度更大、更靠近叶子节点的位置，因此通常译为“最近（的）公共祖先”。

相关词 Related Words

• Tree
• Node
• Root
• Ancestor
• Descendant
• Binary Tree
• Depth
• Subtree
• Traversal
• Euler Tour
• Range Minimum Query
• LCA

文献与作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在树与相关算法讨论中常出现“lowest common ancestor”。
• Competitive Programming（Steven & Felix Halim）：竞赛算法语境中常以 LCA/lowest common ancestor 作为经典树上查询问题。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在树结构与算法章节中常提到相关概念与应用场景。